package algorithm.sort;

import org.junit.Test;

import java.util.Arrays;

public class MergeSort3 {

  public static void main(String[] args) {


  }

  int[] arr;

  /**
   * 实现一个并归
   */
  @Test
  public void test1() {
//    this.arr = new int[]{1, 4, 9, 22, 2, 5, 8, 11};
    this.arr = new int[]{4, 1};
    //low 到 mid 从小到大排列， mid 到 high 从小排序
    int low = 0;
    int hight = this.arr.length - 1;
    int mid = (hight + low) / 2;

    merge(low, mid, hight);

    System.out.println(Arrays.toString(this.arr));
  }

  /**
   * 这个 方法 是排序的核心方法
   * low 是this.arr的头部下标， high 是this.arr的尾部下标 ,mid 左右的的数组已经从小到大排列
   */
  public void merge(int low, int mid, int high) {
    if (low >= high) {
      return;
    }

    //额外的内存空间，[low，mid]
    int[] tmparr = new int[mid - low + 1];
    for (int i = low, tmp = 0; i <= mid; i++, tmp++) {
      tmparr[tmp] = this.arr[i];
    }

    //tmparr 的开始位置
    int ai = 0;
    //本轮 this.arr 的开始位置
    int bi = mid + 1;

    int current = low;
    while (true) {
      if (ai >= tmparr.length && bi > high) break;
      if (ai >= tmparr.length) {
        this.arr[current] = this.arr[bi++];
      } else if (bi > high) {
        this.arr[current] = tmparr[ai++];
      } else if (tmparr[ai] < this.arr[bi]) {
        this.arr[current] = tmparr[ai++];
      } else if (tmparr[ai] > this.arr[bi]) {
        this.arr[current] = this.arr[bi++];
      }
      current++;
    }


  }

  /**
   * 归并排序
   */
  @Test
  public void test2() {
//    this.arr = new int[]{1, 4, 9, 22, 2, 5, 8, 11};
    this.arr = new int[]{10, 4, 22, 2, 8, 1};


    sort(0, this.arr.length - 1);

    System.out.println(Arrays.toString(this.arr));
  }

  public void sort(int low, int high) {

    if (low >= high) return;
    int mid = (low + high) / 2;
    sort(low, mid);
    sort(mid + 1, high);

    merge(low, mid, high);
  }

}
